{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Custom Sort String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: customSortString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #自定义字符串排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串 <code>order</code> 和 <code>s</code> 。<code>order</code> 的所有字母都是 <strong>唯一</strong> 的，并且以前按照一些自定义的顺序排序。</p>\n",
    "\n",
    "<p>对 <code>s</code> 的字符进行置换，使其与排序的&nbsp;<code>order</code>&nbsp;相匹配。更具体地说，如果在&nbsp;<code>order</code>&nbsp;中的字符 <code>x</code> 出现字符 <code>y</code> 之前，那么在排列后的字符串中， <code>x</code>&nbsp;也应该出现在 <code>y</code> 之前。</p>\n",
    "\n",
    "<p>返回 <em>满足这个性质的 <code>s</code> 的任意一种排列&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> order = \"cba\", s = \"abcd\"\n",
    "<strong>输出:</strong> \"cbad\"\n",
    "<strong>解释:</strong> \n",
    "“a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。\n",
    "因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> order = \"cbafg\", s = \"abcd\"\n",
    "<strong>输出:</strong> \"cbad\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= order.length &lt;= 26</code></li>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 200</code></li>\n",
    "\t<li><code>order</code>&nbsp;和&nbsp;<code>s</code>&nbsp;由小写英文字母组成</li>\n",
    "\t<li><code>order</code>&nbsp;中的所有字符都 <strong>不同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [custom-sort-string](https://leetcode.cn/problems/custom-sort-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [custom-sort-string](https://leetcode.cn/problems/custom-sort-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cba\"\\n\"abcd\"', '\"cbafg\"\\n\"abcd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order = [ i for i in order if i in s]\n",
    "        add_list = [ i for i in s if i not in order]\n",
    "        for idx, j in enumerate(order):\n",
    "            while order.count(j) < s.count(j): \n",
    "                order.insert(idx,j)\n",
    "        order +=sorted(add_list)\n",
    "        return ''.join(order)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        index_order=[]\n",
    "        other = []\n",
    "        for a in s:\n",
    "            if a in order:\n",
    "                index_order.append(order.index(a))\n",
    "            else:\n",
    "                other.append(a)\n",
    "        index_order.sort()\n",
    "        index_order=index_order[::-1]\n",
    "        for b in index_order:\n",
    "            other.append(order[b])\n",
    "        \n",
    "        other = other[::-1]\n",
    "\n",
    "        return \"\".join(other)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        freq = Counter(s)\n",
    "        ans = list()\n",
    "        for ch in order:\n",
    "            if ch in freq:\n",
    "                ans.extend([ch] * freq[ch])\n",
    "                freq[ch] = 0\n",
    "        for (ch, k) in freq.items():\n",
    "            if k > 0:\n",
    "                ans.extend([ch] * k)\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_dict = {order[i]: i for i in range(len(order))}\n",
    "        s = [(c, order_dict[c] if c in order_dict else 0)  for c in s]\n",
    "        return ''.join([m[0] for m in sorted(s, key=lambda x: x[1])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        val = defaultdict(int)\n",
    "        s = list(s)\n",
    "        for i in range(len(order)):\n",
    "            val[order[i]] = i + 1\n",
    "        s.sort(key = lambda x: val[x])\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        result = ''\n",
    "        freq = Counter(s)\n",
    "\n",
    "        for ch in order:\n",
    "            if ch in freq:\n",
    "                while freq[ch] > 0:\n",
    "                    result += ch\n",
    "                    freq[ch] -= 1\n",
    "\n",
    "        for ch in freq:\n",
    "            while freq[ch] > 0:\n",
    "                result += ch\n",
    "                freq[ch] -= 1\n",
    "\n",
    "        return result\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        return \"\".join(sorted(s, key=lambda x:order.find(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_dict = {order[i]: i for i in range(len(order))}\n",
    "        s = [(c, order_dict[c] if c in order_dict else 0)  for c in s]\n",
    "        return ''.join([m[0] for m in sorted(s, key=lambda x: x[1])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        n, m = len(s), len(order)\n",
    "        ans, tmp = [], []\n",
    "        mp = set(order)\n",
    "        d = {order[i] : i for i in range(m)}\n",
    "        for i in range(n):\n",
    "            if s[i] in mp:\n",
    "                size = len(ans)\n",
    "                index = 0\n",
    "                while index < size:\n",
    "                    if d[ans[index]] < d[s[i]]:\n",
    "                        index += 1\n",
    "                    else:\n",
    "                        break\n",
    "                ans.insert(index, s[i])\n",
    "            else:\n",
    "                tmp.append(s[i])\n",
    "        return \"\".join(ans) + \"\".join(sorted(tmp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        ord_m = {}\n",
    "        for i, ch in enumerate(order):\n",
    "            ord_m[ch] = i\n",
    "        return ''.join(sorted(s, key=lambda ch: ord_m[ch] if ch in ord_m else 9999))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        val = defaultdict(int)\n",
    "        for i, ch in enumerate(order):\n",
    "            val[ch] = i + 1\n",
    "        \n",
    "        return \"\".join(sorted(s, key=lambda ch: val[ch]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        dic={i:j for j,i in enumerate(order)}\n",
    "        tmp=sorted(s,key=lambda x:dic.get(x,-1))\n",
    "        return ''.join(tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        weight = defaultdict(int)\n",
    "        for i in range(len(order)):\n",
    "            weight[order[i]] = i + 1\n",
    "        s = list(s)\n",
    "        s.sort(key=lambda c: weight[c])\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        dict2=Counter(s)\n",
    "        res=''\n",
    "        for k in order:\n",
    "            for _ in range(dict2[k]):\n",
    "                res+=k\n",
    "        \n",
    "        for k,v in dict2.items():\n",
    "            if k not in order:\n",
    "                for _ in range(v):\n",
    "                    res+=k   \n",
    "             \n",
    "        return res\n",
    "        #print(dict1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        sortOrder = {}\n",
    "        sortOrder.update({a:b for a,b in zip('abcdefghijklmnopqrstuvwxyz', range(27+1,27+27))} )\n",
    "        # print(sortOrder)\n",
    "        sortOrder.update({a:b for a,b in zip(order, range(1,27))} )\n",
    "        # print(sortOrder)\n",
    "        ss = sorted(list(s), key = lambda x: sortOrder[x])\n",
    "        return ''.join(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        mapping = {}\n",
    "        for c in s:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        result = ''\n",
    "        for c in order:\n",
    "            if(c in mapping):\n",
    "                result += c*mapping[c]\n",
    "                del mapping[c]\n",
    "        for c in mapping:\n",
    "            result += c*mapping[c]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        return ''.join(sorted(s,key=lambda x:order.index(x) if x in order else 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        return ''.join(sorted(list(s), key=lambda x:order.find(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        val = defaultdict(int)\n",
    "        for i, ch in enumerate(order):\n",
    "            val[ch] = i + 1\n",
    "        return \"\".join(sorted(s, key=lambda ch: val[ch]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_dict = {}\n",
    "        n = len(order)\n",
    "        for i, val in enumerate(order):\n",
    "            order_dict[val] = i + 1\n",
    "        for i in s:\n",
    "            if i not in order_dict:\n",
    "                order_dict[i] = n\n",
    "                n + 1\n",
    "\n",
    "        return  ''.join(sorted(s, key=lambda item : order_dict[item]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnts = [0]*26\n",
    "        for c in s:\n",
    "            cnts[ord(c)-ord('a')] += 1\n",
    "        ans = ''\n",
    "        for c in order:\n",
    "            num = ord(c)-ord('a')\n",
    "            if cnts[num] >= 0:\n",
    "                ans += c*cnts[num]\n",
    "                cnts[num]=0\n",
    "        for i in range(26):\n",
    "            if cnts[i] > 0:\n",
    "                    ans += chr(i+ord('a')) * cnts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        for c in order:\n",
    "           ans.append(c * cnt[c])\n",
    "           cnt[c] = 0\n",
    "        for c, v in cnt.items():\n",
    "            ans.append(c * v)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        hash_dict = {char: i for i, char in enumerate(order)}\n",
    "        s = list(s)\n",
    "        s.sort(key=lambda x: hash_dict.get(x, len(order)))\n",
    "        s = ''.join(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        orderDict=defaultdict(int)\n",
    "        for i in range(len(order)):\n",
    "            orderDict[order[i]]=i\n",
    "        res=list(s)\n",
    "        res.sort(key=lambda x:orderDict[x])\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_mapping = []\n",
    "        freq = Counter(s)\n",
    "        for i, ch in enumerate(order):\n",
    "            order_mapping.append((ch, i))\n",
    "        \n",
    "        order_mapping.sort(key = lambda x : x[1])\n",
    "\n",
    "        result = []\n",
    "        for ch in order_mapping:\n",
    "            if ch[0] in s:\n",
    "                count = freq[ch[0]]\n",
    "                while count > 0:\n",
    "                    result.append(ch[0])\n",
    "                    count -= 1\n",
    "        \n",
    "        for ch in s:\n",
    "            if ch not in result:\n",
    "                count = freq[ch]\n",
    "                while count > 0:\n",
    "                    result.append(ch)\n",
    "                    count -= 1\n",
    "        \n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        count = {}\n",
    "        for c in s:\n",
    "            count[c] = count.get(c,0) + 1\n",
    "        \n",
    "        orderSet = set()\n",
    "        for c in order:\n",
    "            orderSet.add(c)\n",
    "\n",
    "        res = ''\n",
    "        for c in order:\n",
    "            res += c * count.get(c, 0)\n",
    "        for c in s:\n",
    "            if c not in orderSet:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        results = []\n",
    "        letterCnt = [0] * 26\n",
    "\n",
    "        for letter in s:\n",
    "            idx = ord(letter) - ord('a')\n",
    "            letterCnt[idx] += 1\n",
    "        \n",
    "        for letter in order:\n",
    "            idx = ord(letter) - ord('a')\n",
    "            for _i in range(letterCnt[idx]):\n",
    "                results.append(letter)\n",
    "            letterCnt[idx] = 0\n",
    "        \n",
    "        for idx in range(26):\n",
    "            letter = chr(ord('a') + idx)\n",
    "            for _i in range(letterCnt[idx]):\n",
    "                results.append(letter)\n",
    "        \n",
    "        return ''.join(results)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        for c in order:\n",
    "            ans.append(c * cnt[c])\n",
    "            cnt[c] = 0\n",
    "        for c, v in cnt.items():\n",
    "            ans.append(c * v)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        return \"\".join(sorted(s,key=lambda x:order.find(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_dict = defaultdict(int)\n",
    "        for i, char in enumerate(order):\n",
    "            order_dict[char] = i\n",
    "        s_list = list(s)\n",
    "        s_list.sort(key=lambda x: order_dict[x])\n",
    "        return \"\".join(s_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        mapping = {}\n",
    "        for c in s:\n",
    "            if(c not in mapping):\n",
    "                mapping[c] = 1\n",
    "            else:\n",
    "                mapping[c] += 1\n",
    "        result = ''\n",
    "        for c in order:\n",
    "            if(c in mapping):\n",
    "                result += c*mapping[c]\n",
    "                del mapping[c]\n",
    "        for c in mapping:\n",
    "            result += c*mapping[c]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        dt= collections.defaultdict(int)\n",
    "#        back = {}\n",
    "\n",
    "\n",
    "\n",
    "        for idx, o in enumerate (order):\n",
    "            dt[o] = idx\n",
    "            # back[idx] = o\n",
    "        \n",
    "        st = list(s)\n",
    "        st.sort(key = lambda x : dt[x])\n",
    "        return ''.join(st)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def customSortString(self, order: str, s: str) -> str:\n",
    "#         d = {c: i for i, c in enumerate(order)}\n",
    "#         return \"\".join(sorted(s, key=lambda x: d.get(x, 0)))\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        ans = []\n",
    "        for c in order:\n",
    "            ans.append(c * cnt[c])\n",
    "            cnt[c] = 0\n",
    "        for c, v in cnt.items():\n",
    "            ans.append(c * v)\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        # time complexity: o(n+k)\n",
    "        # space complexity: o(k)\n",
    "        \"\"\"\n",
    "        遍历s，使用数组或哈希表统计每个字符出现的次数。\n",
    "        随后遍历order，如果其在s中出现了k次，就在答案的末尾添加k个c，并将数组或哈希表中对应的次数置为0。\n",
    "        最后我们遍历一次哈希表，对于所有次数非0的键值对(c,k)，在答案的末尾添加k个c(在s中出现，在order中没出现)\n",
    "        \"\"\"\n",
    "        freq = defaultdict(int)\n",
    "        for ch in s:\n",
    "            freq[ch] += 1\n",
    "        \n",
    "        new_str = []\n",
    "        for ch in order:\n",
    "            new_str.append(ch * freq[ch])\n",
    "            freq[ch] = 0\n",
    "        \n",
    "        for k, v in freq.items():\n",
    "            if v:\n",
    "                new_str.append(k * v)\n",
    "\n",
    "        return \"\".join(new_str)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        counter=dict()\n",
    "        for ch in order:\n",
    "            counter[ch]=order.index(ch)\n",
    "        res=['']*len(s)\n",
    "        part=''\n",
    "        for ch in s:\n",
    "            if ch in counter:\n",
    "                res[counter[ch]]+=ch\n",
    "            else:\n",
    "                part+=ch\n",
    "        return ''.join(res)+part\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        # return \"\".join(sorted(s,key=lambda x:order.find(x)))\n",
    "        freq=Counter(s)\n",
    "        ans=[]\n",
    "        for ch in order:\n",
    "            if ch in freq:\n",
    "                ans+=[ch]*freq[ch]\n",
    "                freq[ch]=0\n",
    "        for ch,cnt in freq.items():\n",
    "            if cnt>0:\n",
    "                ans+=[ch]*cnt\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        l1 = set(order)\n",
    "        l2 = {}\n",
    "        l3 = \"\"\n",
    "        target = \"\"\n",
    "        for i in range (len(s)):\n",
    "            if s[i] in l1:\n",
    "                if s[i] not in l2:\n",
    "                    l2[s[i]] = 1\n",
    "                else:\n",
    "                    l2[s[i]] += 1\n",
    "            else:\n",
    "                l3 += s[i]\n",
    "        for i in range (len(order)):\n",
    "            if order[i] in l2:\n",
    "                target += order[i] * l2[order[i]]\n",
    "        return target + l3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        s = list(s)\n",
    "        s.sort(key=lambda x:order.find(x) if x in order else 0)\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        \n",
    "        order = order[::-1]\n",
    "         \n",
    "        return \"\".join(sorted(s,key=lambda x:(order.find(x)),reverse=True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        hash_dict = {}\n",
    "        for ch in s:\n",
    "            if ch not in hash_dict:\n",
    "                hash_dict[ch] = 1\n",
    "            else:\n",
    "                hash_dict[ch] += 1\n",
    "        res = \"\"\n",
    "        for ch in order:\n",
    "            if ch in hash_dict:\n",
    "                res += ch * hash_dict[ch]\n",
    "                hash_dict.pop(ch, None)\n",
    "        for ch, num in hash_dict.items():\n",
    "            res += ch * num\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnts = Counter(s)\n",
    "        ans = []\n",
    "        for c in order:\n",
    "            ans.append(c*cnts[c])\n",
    "        \n",
    "        for c in cnts:\n",
    "            if c not in order:\n",
    "                ans.append(c*cnts[c])\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        d = {}\n",
    "        # 第一个权值1，第二个权值2，。。。没有的给他0\n",
    "        for i, ch in enumerate(order):\n",
    "            d[ch] = i + 1\n",
    "\n",
    "        res = ''.join(sorted(s, key=lambda ch: d.get(ch, 0)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        rank = {}\n",
    "        for i in range(len(order)):\n",
    "            rank[order[i]] = len(rank) + 1\n",
    "        for j in range(len(s)):\n",
    "            if s[j] not in rank:\n",
    "                rank[s[j]] = 0\n",
    "        sorted_s = sorted(s, key=lambda x: rank[x])\n",
    "        ans = ''.join(sorted_s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        s_cnt = Counter(s)\n",
    "        res=''\n",
    "        for c in order:\n",
    "            res+=c*s_cnt[c]\n",
    "        \n",
    "        for key,val in s_cnt.items():\n",
    "            if key in order:\n",
    "                continue\n",
    "            res+=key*val\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "\n",
    "        n = len(order)\n",
    "        temp = [0] * n\n",
    "\n",
    "        freq = dict()\n",
    "        ans = \"\"\n",
    "\n",
    "        for idx,ch in enumerate(order):\n",
    "            freq[ch] = idx\n",
    "        print(freq)\n",
    "\n",
    "        for ch in s:\n",
    "            if ch in freq.keys():\n",
    "                temp[freq[ch]] += 1\n",
    "            else:\n",
    "                ans += (ch)\n",
    "        # print(ans)\n",
    "        # print(temp)\n",
    "        for idx,num in enumerate(temp):\n",
    "            while num > 0:\n",
    "                ans += (order[idx])\n",
    "                num -= 1\n",
    "        return ans\n",
    "        # print(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        val = defaultdict(int)\n",
    "        for i, ch in enumerate(order):\n",
    "            val[ch] = i + 1\n",
    "        \n",
    "        return \"\".join(sorted(s, key=lambda ch: val[ch]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        \n",
    "        check = collections.defaultdict(int)\n",
    "        for i,ch in enumerate(order):\n",
    "            check[ch] = i \n",
    "        saved = collections.defaultdict(list)\n",
    "\n",
    "        for ch in s:\n",
    "            if ch in check:\n",
    "                saved[check[ch]].append(ch)\n",
    "            else:\n",
    "                saved[27].append(ch)\n",
    "        \n",
    "        ans = \"\"\n",
    "        for i in range(28):\n",
    "            if i in saved:\n",
    "                ans += \"\".join(saved[i])\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Need review and recite\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_dict = defaultdict(int)\n",
    "        for i, char in enumerate(order):\n",
    "            order_dict[char] = i\n",
    "        s_list = list(s)\n",
    "        s_list.sort(key=lambda x: order_dict[x])\n",
    "        return \"\".join(s_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        import collections\n",
    "\n",
    "        pos = collections.defaultdict(int)\n",
    "        for i, each in enumerate(order):\n",
    "            pos[each] = i\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        for c in s:\n",
    "            ret.append((c, pos[c]))\n",
    "\n",
    "        return \"\".join([each[0] for each in sorted(ret, key=lambda x: x[1])])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        count = {}\n",
    "        for c in s:\n",
    "            count[c] = count.get(c,0) + 1\n",
    "        \n",
    "        orderSet = set()\n",
    "        for c in order:\n",
    "            orderSet.add(c)\n",
    "\n",
    "        res = ''\n",
    "        for c in order:\n",
    "            res += c * count.get(c, 0)\n",
    "        for c in s:\n",
    "            if c not in orderSet:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        return ''.join(sorted(s, key=lambda x:order.find(x)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        #将所有缺失的键所对应的值默认设置为0，因此在访问缺失的键时，不会发生keyerror错误，不需要检查\n",
    "        #键是否存在\n",
    "        d=defaultdict(int)\n",
    "        for i in range(len(order)):\n",
    "            d[order[i]]=i\n",
    "        #sorted返回一个新的列表，第一个参数为排序目标，key可以指定排序规则\n",
    "        #join是字符串拼接函数\n",
    "        return \"\".join(sorted(s,key=lambda c:d[c]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        hashmap = {}\n",
    "        for i in range(len(order)):\n",
    "            hashmap[order[i]] = i\n",
    "        \n",
    "        c_in_order = []\n",
    "        c_not_in_order = []\n",
    "        for c in s:\n",
    "            if c in hashmap:\n",
    "                c_in_order.append((hashmap[c], c))\n",
    "            else:\n",
    "                c_not_in_order.append(c)\n",
    "        c_in_order.sort()\n",
    "        for _, c in c_in_order:\n",
    "            c_not_in_order.append(c)\n",
    "        return \"\".join(c_not_in_order)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        temp = {}\n",
    "        for c in s:\n",
    "            if c in order:\n",
    "                if c in temp:\n",
    "                    temp[c] += 1\n",
    "                else:\n",
    "                    temp[c] = 1\n",
    "\n",
    "        res = \"\"\n",
    "        for c in order:\n",
    "            if c in temp:\n",
    "                count = temp[c]\n",
    "                while count:\n",
    "                    res += c\n",
    "                    count -= 1\n",
    "\n",
    "        for c in s:\n",
    "            if c in order:\n",
    "                continue\n",
    "            else:\n",
    "                res += c\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        res = \"\"\n",
    "        for i in range(len(order)):\n",
    "            res += cnt[order[i]] * order[i]\n",
    "            # del cnt[order[i]]\n",
    "            cnt[order[i]] = 0\n",
    "        for k in cnt:\n",
    "            if cnt[k] > 0:\n",
    "                res += k * cnt[k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnts = Counter(s)\n",
    "        ans = []\n",
    "        for c in order:\n",
    "            ans.append(c*cnts[c])\n",
    "        \n",
    "        for c in set(s):\n",
    "            if c not in order:\n",
    "                ans.append(c*cnts[c])\n",
    "        \n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        p = {v:k for k,v in enumerate(order)}\n",
    "\n",
    "        ans = [None] * len(s)\n",
    "        tmp = []\n",
    "        for k, v in enumerate(s):\n",
    "            if v not in p:\n",
    "                ans[k] = v\n",
    "            else:\n",
    "                tmp.append(v)\n",
    "                \n",
    "        tmp.sort(key=lambda x: p[x])\n",
    "        for k, v in enumerate(ans):\n",
    "            ans[k] = tmp.pop(0) if not v else v\n",
    "\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        \n",
    "        letters = {}\n",
    "        for char in s:\n",
    "            if char in letters:\n",
    "                letters[char] += 1\n",
    "            else:\n",
    "                letters[char] = 1\n",
    "\n",
    "        results = []\n",
    "        for letter in order:\n",
    "            if letter in letters:\n",
    "                for _cnt in range(letters[letter]):\n",
    "                    results.append(letter)\n",
    "                del letters[letter]\n",
    "        for letter, cnt in letters.items():\n",
    "            for _cnt in range(cnt):\n",
    "                results.append(letter)\n",
    "        \n",
    "        return ''.join(results)\n",
    "        \n",
    "\n",
    "'''\n",
    "count each letters in s\n",
    "start from the min-order\n",
    "put the results, then put un-order letters in the last\n",
    "\n",
    "m = len(order)\n",
    "n = len(s)\n",
    "\n",
    "n + m + n\n",
    "\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        from collections import Counter\n",
    "        count = Counter(s)\n",
    "        \n",
    "        ans = ''\n",
    "        for ch in order:\n",
    "            ans += ch * count[ch]\n",
    "            count[ch] = 0\n",
    "        \n",
    "        for ch in count:\n",
    "            if count[ch] != 0:\n",
    "                ans += ch * count[ch]\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        rank = {}\n",
    "        for i in range(len(order)):\n",
    "            rank[order[i]] = len(rank)\n",
    "        ns = [x for x in s if x in rank]\n",
    "        rs = [x for x in s if x not in rank]\n",
    "        \n",
    "        def compare(a, b):\n",
    "            idx_a = rank[a]\n",
    "            idx_b = rank[b]\n",
    "            if idx_a < idx_b:\n",
    "                return -1\n",
    "            elif idx_a > idx_b:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        import functools\n",
    "        key_func = functools.cmp_to_key(compare)\n",
    "        sorted_s = sorted(ns, key=key_func)\n",
    "        sorted_s.extend(rs)\n",
    "        print(sorted_s)\n",
    "        ans = ''.join(sorted_s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        counter = Counter(s)\n",
    "        res = []\n",
    "\n",
    "        for c in order:\n",
    "            if c in counter:\n",
    "                res.append(c * counter[c])\n",
    "                del counter[c]\n",
    "        \n",
    "        for k, v in counter.items():\n",
    "            res.append(k * v)\n",
    "        \n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        sortOrder = {}\n",
    "        # sortOrder.update({a:b for a,b in zip('abcdefghijklmnopqrstuvwxyz', range(27+1,27+27))} )\n",
    "        sortOrder.update({a:b for a,b in zip(order, range(1,27))} )\n",
    "        ss = sorted(list(s), key = lambda x: sortOrder[x] if x in sortOrder else 1)\n",
    "        return ''.join(ss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        S = {}\n",
    "        ans = ''\n",
    "        for x in s:\n",
    "            if x not in S.keys():\n",
    "                S[x] = 1\n",
    "            else:\n",
    "                S[x] += 1\n",
    "        for char in order:\n",
    "            if char in S.keys():\n",
    "                ans += char * S[char]\n",
    "                S[char] = 0\n",
    "        for char in S.keys():\n",
    "            ans += char * S[char]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        n = len(order)\n",
    "        order_dict = {}\n",
    "        for i, ch in enumerate(order):\n",
    "            order_dict[ch] = i \n",
    "        for i, ch in enumerate(s):\n",
    "            if ch not in order_dict:\n",
    "                order_dict[ch] = 999 + i\n",
    "\n",
    "\n",
    "        encode_s = []\n",
    "        for ch in s:\n",
    "            encode_s.append(order_dict[ch])\n",
    "        \n",
    "        id2ch = {}\n",
    "        for k, v in order_dict.items():\n",
    "            id2ch[v] =k\n",
    "\n",
    "        encode_s.sort()\n",
    "\n",
    "        decode_s = []\n",
    "        for i in encode_s:\n",
    "            decode_s.append(id2ch[i])\n",
    "\n",
    "        return ''.join(decode_s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        count = {}\n",
    "        for c in s:\n",
    "            count[c] = count.get(c,0) + 1\n",
    "        \n",
    "        orderSet = set()\n",
    "        for c in order:\n",
    "            orderSet.add(c)\n",
    "\n",
    "        res = ''\n",
    "        for c in order:\n",
    "            res += c * count.get(c, 0)\n",
    "        for c in s:\n",
    "            if c not in orderSet:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\r\n",
    "class Solution:\r\n",
    "    def customSortString(self, order: str, s: str) -> str:\r\n",
    "        counter=Counter(s)\r\n",
    "        ret=[]\r\n",
    "        for c in order:\r\n",
    "            ret.append(c*counter[c])\r\n",
    "            counter[c]=0\r\n",
    "        for k,v in counter.items():\r\n",
    "            if v>0:\r\n",
    "                ret.append(k*v)\r\n",
    "        return ''.join(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        order_map = {c:i for i,c in enumerate(order)}\n",
    "        chars = sorted(s, key = lambda c:order_map.get(c, -1))\n",
    "        return \"\".join(chars)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        l1 = set(order)\n",
    "        l2 = {}\n",
    "        l3 = \"\"\n",
    "        target = \"\"\n",
    "        for i in range (len(s)):\n",
    "            if s[i] in l1:\n",
    "                if s[i] not in l2:\n",
    "                    l2[s[i]] = 1\n",
    "                else:\n",
    "                    l2[s[i]] += 1\n",
    "            else:\n",
    "                l3 += s[i]\n",
    "        for i in range (len(order)):\n",
    "            if order[i] in l2:\n",
    "                target += order[i] * l2[order[i]]\n",
    "        return target + l3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        cnt = [0]*26\n",
    "        for i in s:\n",
    "            cnt[ord(i)-ord('a')]+=1\n",
    "        ans = ''\n",
    "        for i in order:\n",
    "            ans+=i*cnt[ord(i)-ord('a')]\n",
    "            cnt[ord(i)-ord('a')]=0\n",
    "        for i in range(26):\n",
    "            if cnt[i]!='0':\n",
    "                ans += chr(i+ord('a'))*cnt[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "\n",
    "        char2ord = {ch:i for i ,ch in enumerate(order)}\n",
    "\n",
    "        for ch in s:\n",
    "            if ch not in char2ord:\n",
    "                char2ord[ch] = 100000000\n",
    "        # max_val = \n",
    "\n",
    "        s = sorted(list(s), key=lambda a: char2ord[a])\n",
    "        return ''.join(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        chs = [0] * 26\n",
    "        for ch in s:\n",
    "            chs[ord(ch) - ord('a')] += 1\n",
    "\n",
    "        ans = \"\"\n",
    "        for ch in order:\n",
    "            ans = ans + \"\" + ch * chs[ord(ch) - ord('a')]\n",
    "            chs[ord(ch) - ord('a')] = 0\n",
    "        for i in range(26):\n",
    "            ans = ans + \"\" + chr(i + ord('a')) * chs[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def customSortString(self, order: str, s: str) -> str:\n",
    "        mp=defaultdict(int)\n",
    "        for c in s:\n",
    "            mp[c]+=1\n",
    "        ret=\"\"\n",
    "        for c in order:\n",
    "            ret+=c*mp[c]\n",
    "            mp[c]=0\n",
    "        for c in mp:\n",
    "            if mp[c]!=0:\n",
    "                ret+=c*mp[c]\n",
    "        return ret\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
